/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 25228
 * Date: 2024-08-11
 * Time: 13:39
 */
class Solution3 {
    int preindex=0;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int inend=preorder.length-1;
        return buildTree2(preorder,inorder,0,inend);
    }

    public TreeNode buildTree2(int[] preorder, int[] inorder,int begin,int end){
        if(begin>end){
            return null;
        }
        TreeNode root=new TreeNode(preorder[preindex]);

        int index=find(inorder,begin,end,preorder[preindex]);
        preindex++;

        root.left=buildTree2(preorder,inorder,begin,index-1);

        root.right=buildTree2(preorder,inorder,index+1,end);

        return root;
    }
    public int find(int[] inorder,int begin,int end,int x){
        for(int i=begin;i<=end;i++){
            if(inorder[i]==x){
                return i;
            }
        }
        return -1;
    }
}
